package xio.leetcode.java;


import xio.leetcode.java.base.ListNode;

/**
 * leetcode #92 反转链表 II
 *
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 思路：分两步：
 * 1. 将链表从位置m和n断开，分成三段：
 * M段：root ~ mtail
 * R段：rhead ~ rtail
 * N段：nhead ~ 结尾
 *
 * 2. 将 R 段进行反转
 * 3. 最后R头尾和M段 N段拼接即可
 *
 */
public class LC92_ReverseLinkedList2 {
    public ListNode reverseBetween(ListNode head,int m, int n){
        if (m == n){
            return head;
        }
        // 将链表从位置m和n断开，分成三段
        ListNode tmp = new ListNode(Integer.MIN_VALUE);
        tmp.next = head;
        // 都从头开始
        ListNode mtail = tmp;
        ListNode nhead = tmp;
        // nhead移动到位置n
        while (n-- > 0){
            nhead = nhead.next;
        }
        // rtail 移到位置n，nhead 移到下一个位置，并从n断开链表
        ListNode rtail = nhead;
        nhead = nhead.next;
        rtail.next = null;
        // mtail移到位置m-1
        while (--m > 0){
            mtail = mtail.next;
        }
        // rhead移到m，并从m断开链表
        ListNode rhead = mtail.next;
        mtail.next = null;

        // 反转R段
        ListNode rNewhead = new ListNode(Integer.MIN_VALUE);
        rNewhead.next = nhead;
        ListNode next;
        while (rhead != null){
            next = rhead.next;
            rhead.next = rNewhead.next;

            rNewhead.next = rhead;
            rhead = next;
        }
        mtail.next = rNewhead.next;

        return tmp.next;
    }
}
